package com.seven.leetcode.problems;

import java.util.Arrays;

/**
 * 81. 搜索旋转排序数组 II
 * https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/
 * 级别：Medium
 * <p>
 * 已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。
 * 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，
 * 使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]
 * （下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。
 * 给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。
 * 如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。
 * <p>
 * 示例 1：
 * 输入：nums = [2,5,6,0,0,1,2], target = 0
 * 输出：true
 * <p>
 * 示例 2：
 * 输入：nums = [2,5,6,0,0,1,2], target = 3
 * 输出：false
 *
 * @author : wenguang
 * @date : 2021/3/22 9:26
 */
public class SearchInRotatedSortedArray2 {

    public static void main(String[] args) {
        int[] nums = new int[]{2, 5, 6, 0, 0, 1, 2};
        int target = 3;
        System.out.println("in: \ntarget-> " + target + "\nnums-> " + Arrays.toString(nums));
        boolean result = search(nums, target);
        System.out.println("out: " + result);
    }

    public static boolean search(int[] nums, int target) {
        if (null == nums) {
            return false;
        }

        int length = nums.length;
        if (length == 0) {
            return false;
        }

        int num = nums[0];
        int last = nums[length - 1];
        if (target == num || target == last) {
            return true;
        } else if (target > num) {
            for (int i = 0; i < length; i++) {
                num = nums[i];
                if (num == target) {
                    return true;
                } else if (i < length - 1 && num > nums[i + 1]) {
                    break;
                }
            }
        } else if (target < last) {
            for (int i = length - 1; i >= 0; i--) {
                num = nums[i];
                if (num == target) {
                    return true;
                } else if (i > 0 && num < nums[i - 1]) {
                    break;
                }
            }
        }

        return false;
    }
}
